#include <bits/stdc++.h>

using namespace std;




struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
//根据vector值构建二叉树
TreeNode * gou(vector<int> num){
    if(num.size()==0) return nullptr;
    TreeNode *root=new TreeNode(num[0]);
    queue<TreeNode*> s;
    s.push(root);
    int index=1,len=num.size();
    while(!s.empty()&&index<len){
        TreeNode *p=nullptr,*q=nullptr;
        p=new TreeNode(num[index++]);
        if(index<len) q=new TreeNode(num[index++]);
        TreeNode *r=s.front();s.pop();
        r->left=p;r->right=q;
        s.push(p),s.push(q);
    }
    return root;
}

class Solution1 {
    set<string> st;
public:
    void helper(string str,int index){
        int len=str.length();
        if(index==len-1){
            st.insert(str);
            return;
        }else{
            for(int i=index;i<len;i++){
                if(judge(str,index,i)) continue; //剪支 之前判断过的
                swap(str[i],str[index]);
                helper(str,index+1);
                swap(str[i],str[index]);
            }
        }
    }
    bool judge(string &str,int start,int end){
        for(int i=start;i<end;++i){
            if(str[i]==str[end]) return true;
        }
        return false;
    }

    vector<string> permutation(string s) {
        st.clear();
        
        helper(s,0);
        vector<string> sv;
        for(auto it=st.begin();it!=st.end();it++){
            sv.push_back(*it);
        }
        return sv;
    }
};

class Solution {
    vector<string> st;
public:
    void helper(string &str,int index){
        int len=str.length();
        if(index==len){
            st.push_back(str);
            return;
        }else{
            for(int i=index;i<len;i++){
                if(judge(str,index,i)) continue; //剪支 之前判断过的 剪完支之后，无重复，放心加入
                swap(str[i],str[index]);
                helper(str,index+1);
                swap(str[i],str[index]);
            }
        }
    }
    bool judge(string &str,int start,int end){
        for(int i=start;i<end;++i){
            if(str[i]==str[end]) return true;
        }
        return false;
    }

    vector<string> permutation(string s) {
        st.clear();
        
        helper(s,0);
        return st;
    }
};


int main(){

    Solution s;
    s.permutation("abc");


    return 0;
}